/**
 * Given two arrays of integers, find a pair of values (one value from each array)
 * that you can swap to give the two arrays the same sum.
 * <p>
 * Return an array, where the first element is the element in the first array
 * that will be swapped, and the second element is another one in the second array. If
 * there are more than one answers, return any one of them. If there is no answer,
 * return an empty array.
 * <p>
 * Example:
 * <p>
 * <p>
 * Input: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
 * Output: [1, 3]
 * <p>
 * <p>
 * Example:
 * <p>
 * <p>
 * Input: array1 = [1, 2, 3], array2 = [4, 5, 6]
 * Output: []
 * <p>
 * Note:
 * <p>
 * <p>
 * 1 <= array1.length, array2.length <= 100000
 * <p>
 * <p>
 * Related Topics 数组 哈希表 二分查找 排序 👍 40 👎 0
 */


package com.xixi.basicAlgroithms.hash;

import java.util.HashSet;
import java.util.Set;

public class ID_interview_16_21_SumSwapLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_16_21_SumSwapLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        Set<Integer> ele1 = new HashSet<>();
        Set<Integer> ele2 = new HashSet<>();

        public int[] findSwapValues(int[] array1, int[] array2) {

            int sum1 = 0;
            for (int var : array1) {
                ele1.add(var);
                sum1 += var;
            }

            int sum2 = 0;
            for (int var : array2) {
                ele2.add(var);
                sum2 += var;
            }

            int difference = Math.abs(sum1 - sum2);

            //两个数组差为奇数，无法通过交换相等
            if ((difference & 1) == 1) return new int[]{};
            //sum2 - a2 + a1 = sum1 - a1 + a2;
            //2(a1 - a2) = sum1 - sum2
            //abs(a1-a2) = abs(difference)/2

            //剩下就是两数和, 找到两者元素中能相加为diff的两个元素
            //可能是a2的元素比较小，那么 a1 = a2+diff/2
            for (int a2 : ele2) {
                if (ele1.contains(difference / 2 + a2)) {
                    return new int[]{difference / 2 + a2, a2};
                }
            }
            //可能是a1的元素比较小，那么 a2 = a1+diff/2
            for (int a1 : ele1) {
                if (ele2.contains(difference / 2 + a1)) {
                    return new int[]{a1, difference / 2 + a1};
                }
            }

            return new int[]{};


        }


        public int getSum(int[] array) {

            int sum = 0;
            for (int var : array) {
                sum += var;
            }

            return sum;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}